package org.algorithm.熊猫.数组.三月.第二周;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author 熊猫
 * @date 2022/03/08 11:38 PM
 * @description: 周四作业
 *
 * <p>
 * 给你一个整数数组 nums 和一个整数 k 。请你向 nums 中追加 k 个 未 出现在 nums 中的、互不相同 的 正 整数，并使结果数组的元素和 最小 。
 * <p>
 * 返回追加到 nums 中的 k 个整数之和。
 * <p>
 * 案例：
 * 输入：nums = [1,4,25,10,25], k = 2
 * 输出：5
 * 解释：在该解法中，向数组中追加的两个互不相同且未出现的正整数是 2 和 3 。
 * nums 最终元素和为 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70 ，这是所有情况中的最小值。
 * 所以追加到数组中的两个整数之和是 2 + 3 = 5 ，所以返回 5 。
 * </p>
 * <p>
 * uri:  https://leetcode-cn.com/problems/append-k-integers-with-minimal-sum/
 */
public class 向数组中追加K个整数 {

    @Test
    public void test() {
        int[] nums = {5,6};
        System.out.println(minimalKSum2(nums, 6));
        System.out.println(minimalKSum(nums, 6));

    }


    /**
     * 巨慢的解法 1000ms
     *
     * @param nums
     * @param k
     * @return
     */
    public static long minimalKSum(int[] nums, int k) {
        Arrays.sort(nums);
        long sum = 0;
        int index = 0;
        int sumIndex = 1;
        int length = nums.length;
        for (int i = 1; i <= k; ) {
            if (index > length - 1) {
                long i1 = k - i;
                if (i1 == 1) {
                    sum += sumIndex + sumIndex + 1;
                    break;
                }
                sum += (i1 + 1) / 2 * (sumIndex + (sumIndex + i1));
                sum += (((i1 + 1) % 2) != 0 ? (sumIndex + (sumIndex + i1)) / 2 : 0);
                return sum;
            }
            if (!(nums[index] == sumIndex)) {
                sum += sumIndex;
                i++;
            } else {
                index++;
                if (index < length && nums[index] == sumIndex) {
                    sumIndex--;
                }
            }
            sumIndex++;
        }
        return sum;
    }

    /**
     * 勉强 20 ms
     * @param nums
     * @param k
     * @return
     */
    public static long minimalKSum2(int[] nums, int k) {
        Arrays.sort(nums);
        long sum = 0;
        int index = 0;
        int sumIndex = 1;
        int length = nums.length;
        for (int i = 0; i <= k; ) {
            int yu = k - i;
            if (sumIndex < nums[index] && yu > 0) {
                int temp = Math.min(yu, nums[index] - sumIndex);
                i += temp;
                sum += calculation(sumIndex, sumIndex+temp-1, temp);
                sumIndex += temp;
            } else {
                if (index < length - 1 && nums[index] == nums[index + 1]) {
                    index++;
                    continue;
                }
                index++;
                sumIndex++;
                if (index > length - 1) {
                    if (k - i >0) {
                        sum += calculation(sumIndex, sumIndex + (k - i)-1, k - i);
                    }
                    break;
                }
            }
        }
        return sum;
    }

    @Test
    public void Test1() {
        System.out.println(calculation(5, 7 - 1, 7 - 5));
    }

    public static long calculation(long start, long end, int count) {
        long sum = count / 2 * (start + end);
        sum += (count) % 2 == 1 ? (start + end) / 2 : 0;
        return sum;
    }
}
